package com.snake.win.AI;

import com.badlogic.gdx.Gdx;
import com.snake.win.obj.Snake;
import com.snake.win.obj.FoodObj;
import com.snake.win.obj.GameObj;
import com.snake.win.obj.HeadObj;

import java.util.*;

public class SnakeAi {
//    /**
//     * Make it right；
//     * BFS,不过当蛇去吃完后发现把自己围死就GG了
//     *
//     * @param s 蛇
//     * @param f 目标,这里目标可能不是食物所以单独做参数
//     * @return 能到的话返回去的路径第一步，不能的话返回-1；
//     */

    public Snake.Direction play1(Snake snake) {
        Queue<GameObj> q = new LinkedList<GameObj>();
        Set<String> vis = new HashSet<String>();// 记录访问过的节点
        Map<String, String> path = new HashMap<String, String>();//记录访问的路径,后来用A*算法在Node添加了father节点，这个可以去掉了
        Stack<String> stack = new Stack<String>();//蛇去吃的路径
        Set<String> snkMap=snake.getSafeCopy();

        q.add(snake.headObj);
        while (!q.isEmpty()) {
            GameObj n = q.remove();
            if (n.snake_x == snake.foodObj.snake_x && n.snake_y == snake.foodObj.snake_y) {
                //如果搜到了食物，开始解析路径，因为是从后添加，所以用栈倒回来
                String state = snake.foodObj.toString();
                while (state != null && !state.equals(snake.headObj.toString())) {
                    stack.push(state);
                    state = path.get(state);
                }

                String[] str;
                //有时候食物和头挨着就会导致栈为空
                if (stack.isEmpty()) {
                    str = state.split("-");
                } else str = stack.peek().split("-");
                int x = Integer.parseInt(str[0]);
                int y = Integer.parseInt(str[1]);
                if (x > snake.headObj.snake_x && y == snake.headObj.snake_y) {
                    return Snake.Direction.right;
                }
                if (x < snake.headObj.snake_x && y == snake.headObj.snake_y) {
                    return Snake.Direction.left;
                }
                if (x == snake.headObj.snake_x && y > snake.headObj.snake_y) {
                    return Snake.Direction.up;
                }
                if (x == snake.headObj.snake_x && y < snake.headObj.snake_y) {
                    return Snake.Direction.down;
                }
            }
            GameObj up = new GameObj(n.snake_x, n.snake_y - 1);
            GameObj right = new GameObj(n.snake_x + 1, n.snake_y);
            GameObj down = new GameObj(n.snake_x, n.snake_y + 1);
            GameObj left = new GameObj(n.snake_x - 1, n.snake_y);
            if (!snkMap.contains(up.toString()) && !vis.contains(up.toString())
                    && up.snake_x <= 20 && up.snake_x >= 1
                    && up.snake_y <= 20 && up.snake_y >= 1) {
                q.add(up);
                vis.add(up.toString());
                path.put(up.toString(), n.toString());
            }
            if (!snkMap.contains(right.toString()) && !vis.contains(right.toString())
                    && right.snake_x <= 20 && right.snake_x >= 1
                    && right.snake_y <= 20 && right.snake_y >= 1) {
                q.add(right);
                vis.add(right.toString());
                path.put(right.toString(), n.toString());
            }
            if (!snkMap.contains(down.toString()) && !vis.contains(down.toString())
                    && down.snake_x <= 20 && down.snake_x >= 1
                    && down.snake_y <= 20 && down.snake_y >= 1) {
                q.add(down);
                vis.add(down.toString());
                path.put(down.toString(), n.toString());
            }
            if (!snkMap.contains(left.toString()) && !vis.contains(left.toString())
                    && left.snake_x <= 20 && left.snake_x >= 1
                    && left.snake_y <= 20 && left.snake_y >= 1) {
                q.add(left);
                vis.add(left.toString());
                path.put(left.toString(), n.toString());
            }
        }
        return Snake.Direction.no;
    }

    /**
     * Make it right+   //make it fast有点难
     * <p>
     * 如果不可以吃食物就追尾巴，可以吃就先派一条虚拟蛇去吃，如果吃到食物后还可以去追尾巴那就去吃，否者先追尾巴，直到去吃食物后也是安全的,就去吃。
     * 如果不可以吃食物也不能追尾巴就随机走，这应该是小概率事件
     *
     * @return 方向
     */

    public Snake.Direction play2(Snake snake) {
        Snake virSnake = new Snake();
        virSnake.setMap((HashSet<String>) snake.getSafeCopy());
        virSnake.bodyObjList=new ArrayList<>();
        for (GameObj bodyObj: snake.bodyObjList){
            virSnake.bodyObjList.add(new GameObj(bodyObj.snake_x, bodyObj.snake_y));
        }

        virSnake.headObj=new HeadObj(snake.headObj.snake_x, snake.headObj.snake_y);
        virSnake.foodObj=new FoodObj(snake.foodObj.snake_x, snake.foodObj.snake_y);
        virSnake.tailobj=new GameObj(snake.tailobj.snake_x, snake.tailobj.snake_y);
        int virtailX = 0;
        int virtailY = 0;

        //真蛇去吃食物的方向
        Snake.Direction realGoTofoodDir = play1(snake);
        //如果吃得到食物
        if (realGoTofoodDir != Snake.Direction.no) {
            //派虚拟蛇去吃
            while (!virSnake.headObj.toString().equals(snake.foodObj.toString())) {
                virtailX=virSnake.bodyObjList.get(virSnake.bodyObjList.size()-1).snake_x;
                virtailY=virSnake.bodyObjList.get(virSnake.bodyObjList.size()-1).snake_y;
                virSnake.move(play1(virSnake));
            }
            //虚拟蛇到尾巴去的方向
            virSnake.tailobj = new GameObj();
            virSnake.tailobj.snake_x=virtailX;
            if(virtailX==0)
            {
                Gdx.app.log("virtailX","0");
            }
            virSnake.tailobj.snake_y=virtailY;
            Snake.Direction goToDailDir = Asearch(virSnake, virSnake.tailobj);
            //如果虚拟蛇吃完能去尾巴，真蛇就去吃
            if (goToDailDir != Snake.Direction.no) return realGoTofoodDir;
            else {
                snake.c++;
                /**
                 * 如果吃到后不能去自己尾巴，就跟着蛇尾跑
                 * 这里可能无限跟着蛇尾跑，主要原因是我追尾巴也用的BFS，追尾巴应该走最远距离
                 * 最远距离可以用A*算法，也就是bfs加权值贪心
                 */
                if (snake.c < 400)
                    return Asearch(snake, snake.tailobj);
                else {
//						System.out.println("ok");
                    return realGoTofoodDir;//直接去吃算了
                }
            }
        } else {// 如果吃不到食物
            //真蛇到尾巴去的方向
            Snake.Direction realGoToDailDir = Asearch(snake, snake.tailobj);
            if (realGoToDailDir == Snake.Direction.no) {
                // 如果吃不了食物也到不了尾巴就随机走（听天由命）
                realGoToDailDir = randomDir();
//                int i = 0;
//                while (!objManager.canMove(realGoToDailDir)) {
//                    //这里可能死循环，四面都不能走
//                    realGoToDailDir = randomDir();
//                    i++;
//                    if (i > 300) return -1;//防死循环，只能GG了
//                }
                return realGoToDailDir;
            }
            return realGoToDailDir;
        }
    }

    /**
     * A*找最远路径
     *
     * @param s
     * @param f
     * @return
     */
    public Snake.Direction Asearch(Snake s, GameObj f) {
        ArrayList<GameObj> openList = new ArrayList<GameObj>();
        ArrayList<GameObj> closeList = new ArrayList<GameObj>();
        Stack<GameObj> stack = new Stack<GameObj>();//蛇去吃的路径
        openList.add(s.headObj);// 将开始节点放入开放列表;
        s.headObj.H=(dis(s.headObj, f));

        while (!openList.isEmpty()) {
            GameObj now = null;
            int max = -1;
            for (GameObj n : openList) {//我们找F值最大的(说明离目标最远),如果有相同我们选的排在后面的也就是最新添加的。
                if (n.G+n.H >= max) {
                    max = n.G+n.H;
                    now = n;
                }
            }
            // 把当前节点从开放列表删除, 加入到封闭列表;
            openList.remove(now);
            closeList.add(now);
            //四个方向的相邻节点
            GameObj up = new GameObj(now.snake_x, now.snake_y + 1);
            GameObj down = new GameObj(now.snake_x, now.snake_y - 1);
            GameObj left = new GameObj(now.snake_x-1, now.snake_y );
            GameObj right = new GameObj(now.snake_x+1, now.snake_y );

            ArrayList<GameObj> temp = new ArrayList<GameObj>(4);
            temp.add(up);
            temp.add(right);
            temp.add(down);
            temp.add(left);
            for (GameObj n : temp) {
                // 如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,则什么操作也不执行,继续检验下一个节点;
                if (s.getMap().contains(n.toString()) || closeList.contains(n)
                        || n.snake_x > 20 || n.snake_x < 1
                        || n.snake_y > 20 || n.snake_y < 1)
                    continue;

                // 如果该相邻节点不在开放列表中,则将该节点添加到开放列表中,
                // 并将该相邻节点的父节点设为当前节点,同时保存该相邻节点的G和H值,F值的计算直接我写在了Node类里
                if (!openList.contains(n)) {
//					System.out.println("ok");
                    n.father=now;
                    n.G=now.G + 1;
                    n.H=dis(n, f);
                    openList.add(n);
                    // 当终点节点被加入到开放列表作为待检验节点时, 表示路径被找到,此时终止循环,返回方向;
                    if (n.equals(f)) {

                        //从目标节点往前找，....卧槽这里有个坑，node不能用f，因为f与找到的节点虽然坐标相同但f没有记录father
                        GameObj node = openList.get(openList.size() - 1);
                        while (node != null && !node.equals(s.headObj)) {
                            stack.push(node);
                            node = node.father;
                        }
                        int x = stack.peek().snake_x;
                        int y = stack.peek().snake_y;
                        if (x > s.headObj.snake_x && y == s.headObj.snake_y) {
                            return Snake.Direction.right;
                        }
                        if (x < s.headObj.snake_x && y == s.headObj.snake_y) {
                            return Snake.Direction.left;
                        }
                        if (x == s.headObj.snake_x && y > s.headObj.snake_y) {
                            return Snake.Direction.up;
                        }
                        if (x == s.headObj.snake_x && y < s.headObj.snake_y) {
                            return Snake.Direction.down;
                        }
                    }
                }
                // 如果该相邻节点在开放列表中,
                // 则判断若经由当前节点到达该相邻节点的G值是否大于或小于(这里找最远用大于)原来保存的G值,若大于或小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节点的G和F值.
                if (openList.contains(n)) {
                    if (n.G > (now.G + 1)) {
                        n.father=now;
                        n.G=now.G + 1;
                    }
                }
            }
        }
        // 当开放列表为空,表明已无可以添加的新节点,而已检验的节点中没有终点节点则意味着路径无法被找到,此时也结束循环返回-1;
        return Snake.Direction.no;
    }

    /**
     * 计算曼哈顿距离
     *
     * @param src
     * @param des
     * @return
     */
    public int dis(GameObj src, GameObj des) {
        return Math.abs(src.snake_x - des.snake_x) + Math.abs(src.snake_y - des.snake_y);
    }

    /**
     * 随机生产方向
     *
     * @return
     */
    public Snake.Direction randomDir() {
        Random r = new Random();
        int dir = r.nextInt(4);
        if (dir == 0) return Snake.Direction.up;
        else if (dir == 1) return Snake.Direction.down;
        else if (dir == 2) return Snake.Direction.right;
        else return Snake.Direction.left;
    }
}
